package greedy;

/**
 * Created with IntelliJ IDEA.
 * Description: 738. 单调递增的数字
 * User: Li_yizYa
 * Date: 2025/6/30
 * Time: 19:45
 */
public class Solution16 {
    /**
     * 贪心
     * @param n
     * @return
     */
    public int monotoneIncreasingDigits1(int n) {
        if (n <= 0) {
            return n;
        }
        String s = String.valueOf(n);
        char[] str = s.toCharArray();
        int start = s.length();
        for (int i = s.length() - 2; i >= 0; i--) {
            if (str[i] > str[i + 1]) {
                str[i]--;
                start = i + 1;
            }
        }
        for (int i = start; i < s.length(); i++) {
            str[i] = '9';
        }
        return Integer.parseInt(String.valueOf(str));
    }
    /**
     * 暴力解法，时间复杂度太大，通过不了
     * @param n
     * @return
     */
    public int monotoneIncreasingDigits(int n) {
        if (n <= 0) {
            return n;
        }
        for (int i = n; i > 0; i--) {
            if (check(i)) {
                return i;
            }
        }
        return 0;
    }
    private boolean check(int num) {
        int max = 10;
        while (num > 0) {
            int tmp = num % 10;
            if (tmp <= max) {
                max = tmp;
            } else {
                return false;
            }
            num /= 10;
        }
        return true;
    }
}
